package com.alex.program;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。
 * 注意，不是必须有这些素因子，而是必须不包含其他的素因子。
 *
 * 例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
 *
 * 示例 1：
 *
 * 输入：k = 5
 * 输出：9
 */
public class 第K个数 {

    public static void main(String[] args) {
        int k = 5;
        System.out.println(getKthMagicNumber(k));
    }

    public static int getKthMagicNumber(int k) {
        int[] factors = {3, 5, 7};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int magic = 0;
        for (int i = 0; i < k; i++) {
            // heap 是自增的，所以每次取最小的; 到达K的时候, 既是需要的数据
            // seen 防止heap中重复添加了元素, 导致数据重复, 取出来的数据是错误的
            long curr = heap.poll();
            magic = (int) curr;
            // 子循环, 代表的所有乘数
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return magic;
    }
}
